1. Field of the Invention
This invention pertains generally to parallel leading one/zero detection implementations. More particularly, the invention is an optimized system and method for a parallel leading one/zero detection in computer architectures.
2. The Prior Art
In microelectronics, the detection of leading zeros in a number is often required. For example, in floating-point addition, the result of an operation may require a left shift during normalization, as is known in the art.
Normalization is normally carried out using leading one/zero detection (LOZD) or leading one/zero anticipation (LOZA). In one example, a leading one/zero detector receives the result of the floating point addition, and counts the number of preceding zeros or ones in the result. This count is used to drive a shifter unit to produce the final normalized result.
Accordingly, there is an ongoing need for a system and method for detecting leading zeros and ones which improves the speed of the leading zero/one detection process. The present invention satisfies these needs, as well as others, and generally overcomes the deficiencies found in the background art.
The present invention is an apparatus and method for parallel leading zero/one detection using a nibble calculation scheme. The invention further relates to machine readable media on which are stored embodiments of the present invention. It is contemplated that any media suitable for retrieving instructions is within the scope of the present invention. By way of example, such media may take the form of magnetic, optical, or semiconductor media. The invention also relates to data structures that contain embodiments of the present invention, and to the transmission of data structures containing embodiments of the present invention.
The invention operates upon an operand, identified as OPERAND A. OPERAND A is represented by a plurality of nibbles, each nibble comprising four bits. For example, if OPERAND A comprises a thirty-two (32) bit number, OPERAND A is represented by eight (8) nibbles. Each nibble has a corresponding nibble placement within OPERAND A corresponding to a relative Nibble order of significance. For example, in the 32-bit OPERAND A example, Nibble 7 corresponds to bits 31, 30, 29, and 28 of OPERAND A, Nibble 6 corresponds to bits 27, 26, 25, and 24, Nibble 5 corresponds to bits 23, 22, 21 and 20, and Nibble 0 corresponds to bits 3, 2, 1 and 0. As will be readily apparent to those skilled in the art, each of the other nibbles 1, 2, 3, and 4 corresponds to bits associated with the nibble""s placement within OPERAND A.
Each nibble has a corresponding relative nibble order of significance, such that nibbles having higher bits will have a higher order of significance than nibbles having lower bits. For example, Nibble 7 comprising bits 31, 30, 29, and 28 will have a higher order of significance than Nibble 6 corresponding to bits 27, 26, 25 and 24 since bits 31, 30, 29, and 28 have a higher order of significance than bits 27, 26, 25 and 24. Accordingly, Nibble n will have a higher order of significance than Nibble (nxe2x88x921).
According to first embodiment of the present invention, the method for detecting leading zeros in a number comprises calculating a leading zero count for each nibble in parallel; associating with each nibble count calculation a bit value inversely corresponding to the nibble""s order of significance; and selecting the nibble count calculation and its associated bit value which corresponds to the highest order nibble without all zero values.
According to another embodiment of the invention, the leading zero detector apparatus comprises a select circuit which receives as its input the number; a plurality of nibble analyzers, one nibble analyzer for each of the nibbles, each said nibble analyzer having as its input a corresponding nibble; and a filter circuit operatively coupled to said select circuit and said plurality of nibble analyzers.
It will be apparent to those skilled in the art having the benefit of this disclosure that the invention is also suitable for detecting leading ones using the parallel nibble calculation scheme of the present invention.